/*
 * @lc app=leetcode.cn id=377 lang=golang
 *
 * [377] 组合总和 Ⅳ
 */

// @lc code=start
func combinationSum4(nums []int, target int) int {
	n := len(nums)
	dp := make([]int, target+1)
	// for i, _ := range dp {
	// 	dp[i] = make([]int, n+1)
	// }
	// dp[0][0] = 1
	dp[0] = 1
	for i := 0; i <= target; i++ {
		for j := 1; j <= n; j++ {
			if nums[j-1] <= i {
				dp[i] += dp[i-nums[j-1]]
			}

		}
	}
	// fmt.Println(dp)
	return dp[target]

}

// @lc code=end

